#include <cstdio>
#include <vector>

const int N = 1005;
int n, m, q, ans[N][N], fa[N];

struct Node {
  int x, y, t;
  Node(int _x, int _y, int _t) : x(_x), y(_y), t(_t) {}
  inline bool operator<(const Node &rhs) const { return t < rhs.t; }
};

std::vector<Node> vec;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("pictionary.in", "r", stdin);
  freopen("pictionary.out", "w", stdout);
#endif
#endif

  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) {
      vec.push_back(Node(i, j, m + 1 - gcd(i, j)));
    }
  for (std::vector<Node>::iterator i = vec.begin(); i != vec.end(); ++i) {
    if (find(i->x) != find(i->y)) {
      fa[find(i->x)] = find(i->y);
    }
  }
  for (int i = 1, x, y; i <= q; ++i) {
    scanf("%d%d", &x, &y);
    printf("%d\n", ans[x][y]);
  }
  return 0;
}